home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / delete.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  16KB  |  679 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /** 
  9.      delete.c -- routines to add and delete parts of the digraph data structure
  10.    **/
  11.  
  12. #include "malloc.h"
  13. #include "attribute.h"
  14. #include "digraph.h"
  15. #include "debug.h"
  16.  
  17. OUTEDGE *get_edge();
  18. NODE *get_prev_node(), *get_next_node();
  19. NODE *prev_dummy(), *next_dummy();
  20. LEVEL *find_level();
  21. char **dispose_out_edge();
  22. short hash();
  23. DeleteEdge();
  24.  
  25. DeleteNode(digraph, node)
  26. DIGRAPH *digraph;
  27. NODE *node;
  28.   /** 
  29.      DeleteNode removes a node from the digraph structure.
  30.      First it removes associated in and out edges.  Then it fixes up the
  31.      successor sets of its predecessors, and the predecessor sets of its 
  32.      successors, deleting any associating dummy nodes along the way.
  33.      Finally, it releases the space used by the node.
  34.    **/
  35. {
  36.     NODE *next_node, *prev_node, *decomp;
  37.     VNO vno, prev_vno, next_vno;
  38.     OUTEDGE *out_edge;
  39.     INEDGE *in_edge;
  40.    
  41.       /**
  42.      Delete the associated in and out edges.
  43.      If its a dummy node, we must delete the edges between the previous 
  44.      non-dummy node and the next non-dummy node.
  45.        **/
  46.     if (Is_dummy(node))
  47.     {
  48.     int i;
  49.  
  50.         prev_node = get_prev_node(digraph, node);
  51.         next_node = get_next_node(digraph, node);
  52.  
  53.     for (i = max_edges(prev_node, next_node); i > 0; i++)
  54.     {
  55.         if (get_edge(digraph, prev_node, next_node, i) != NULL)
  56.         {
  57.             dispose_edge(digraph, prev_node, next_node, i);
  58.         }
  59.     }
  60.     }
  61.     else if (Coalescer(node))
  62.     {
  63.     delete_coalescer_in_out(digraph, node);
  64.     }
  65.     else
  66.       /**
  67.      Fix up in-edge lists of nodes on out-edge list and out-edge lists
  68.          of nodes on in-edge list.
  69.      Note:  if you can delete coalesced members without deleting the 
  70.      coalescer, this won't work, because it doesn't take into account
  71.      the links to/from coalescer nodes which this node might be
  72.      a member of.  But currently you can't do that.
  73.        **/
  74.     {
  75.     all_out_edges(node, out_edge)
  76.     loop
  77.             dispose_edge(digraph, node, Node(digraph, To_vno(out_edge)), 
  78.              Ord(out_edge));
  79.         endloop
  80.  
  81.         all_in_edges(node, in_edge)
  82.         loop
  83.             dispose_edge(digraph, Node(digraph, From_vno(in_edge)), node,
  84.              Ord(in_edge));
  85.         endloop
  86.     }
  87.  
  88.       /**
  89.      Fix up successor sets of predecessors, remove predecessor dummy nodes.
  90.          Fix up predecessor sets of successors, remove successor dummy nodes.
  91.        **/
  92.     each_element(Ante_set(node), prev_vno)
  93.     loop
  94.         remove_ante_links(digraph, node, Node(digraph, prev_vno));
  95.     endloop
  96.  
  97.     each_element(Succ_set(node), next_vno)
  98.     loop
  99.         remove_succ_links(digraph, node, Node(digraph, next_vno));
  100.     endloop
  101.  
  102.       /* Unlink node from level structure, remove its vertex, free up space. */
  103.     dispose_node(digraph, node);
  104. } /* DeleteNode */
  105.  
  106. delete_coalescer_in_out(digraph, node)
  107. DIGRAPH *digraph;
  108. NODE *node;
  109.   /** 
  110.      recursively delete all in and out edges of the elements of 
  111.      a coalescer node
  112.    **/
  113. {
  114.     NODE *decomp;
  115.     VNO vno;
  116.     OUTEDGE *out_edge;
  117.     INEDGE *in_edge;
  118.  
  119.     each_element(Expansion(node), vno)  
  120.     loop
  121.        decomp = Node(digraph, vno);
  122.  
  123.     if (Coalescer(decomp))
  124.       /* then recurse */
  125.     {
  126.         delete_coalescer_in_out(digraph, decomp);
  127.     }
  128.     else
  129.     {
  130.         all_out_edges(decomp, out_edge)
  131.             loop
  132.                 dispose_edge(digraph, decomp, Node(digraph, To_vno(out_edge)),
  133.                   Ord(out_edge));
  134.             endloop
  135.  
  136.             all_in_edges(decomp, in_edge)
  137.             loop
  138.                 dispose_edge(digraph, Node(digraph, From_vno(in_edge)), decomp,
  139.                  Ord(in_edge));
  140.             endloop
  141.     }
  142.     endloop
  143. }
  144.  
  145. DeleteEdge(digraph, from_node, to_node, ord)
  146. DIGRAPH *digraph;
  147. NODE *from_node, *to_node;
  148. int ord;
  149.   /**
  150.      DeleteEdge deletes the edge from from_node to to_node.  If there is only
  151.      one edge from from_node to to_node, it also deletes intervening dummy 
  152.      nodes and the associated links.
  153.    **/
  154. {
  155.     NODE *prev_node, *next_node;
  156.     VNO next_vno;
  157.  
  158.     if (num_edges(from_node, to_node) == 1)
  159.     {
  160.       /**
  161.          There is only one edge.  Delete intervening dummy nodes and 
  162.          associated links.
  163.          First, search for the successor to from_node that goes to 
  164.          to_node.  Note that if there are no intervening dummy nodes,
  165.          this loop changes nothing, which is just fine.
  166.        **/
  167.         each_element(Succ_set(from_node), next_vno)
  168.         loop
  169.         next_node = Node(digraph, next_vno);
  170.     
  171.         if (Is_dummy(next_node)
  172.             && get_next_node(digraph, next_node) == to_node) 
  173.           /* found the right dummy */
  174.         {
  175.             remove_link(from_node, next_node);
  176.  
  177.             do
  178.             {
  179.                 prev_node = next_node;
  180.             next_node = next_dummy(digraph, next_node);
  181.             remove_link(prev_node, next_node);
  182.             dispose_node(digraph, prev_node);        
  183.             } while (Is_dummy(next_node));
  184.  
  185.             break;
  186.         }
  187.         endloop;
  188.     
  189.         remove_link(from_node, to_node);
  190.     }
  191.  
  192.     dispose_edge(digraph, from_node, to_node, ord);
  193. } /* DeleteEdge */
  194.  
  195. dispose_node(digraph, node)
  196. DIGRAPH *digraph;
  197. NODE *node;
  198.   /**
  199.      dispose_node removes the sets and attributes pointed to by node, removes
  200.      the associated vertex, unlinks the node from the level structure,
  201.      and frees up the space occupied by the node.
  202.      If node is a coalescer, it first recursively calls itself on all the 
  203.      elements of the node.
  204.    **/
  205. {
  206.     VNO vno;
  207.  
  208.     if (Coalescer(node))
  209.     {
  210.       /* dispose of all members of a coalescer recursively */
  211.         each_element(Expansion(node), vno)  
  212.         loop
  213.             dispose_node(digraph, Node(digraph, vno));
  214.         endloop
  215.     }
  216.  
  217.     vno = Vno(node);
  218.     remove_from_level(digraph, node);
  219.     dispose(Ante_set(node));
  220.     dispose(Succ_set(node));
  221.     dispose(Expansion(node));
  222.     dispose_attr(node->attributes, NNodeAttr(digraph));
  223.  
  224.     dispose_vertex(digraph, Name(node));
  225.     dispose(node);
  226.     Node(digraph, vno) = NULL;
  227. } /* dispose_node */
  228.  
  229. dispose_attr(attr, num)
  230. char **attr;
  231. int num;
  232.   /* dispose of an array of character pointers. */
  233. {
  234.     int i;
  235.  
  236.     for (i = 0; i < num; i++)
  237.     {
  238.         dispose(attr[i]);
  239.     }
  240.  
  241.     dispose(attr);
  242. }
  243.  
  244. dispose_vertex(digraph, name)
  245. DIGRAPH *digraph;
  246. char *name;
  247.   /** 
  248.      dispose_vertex locates the vertex identified by name and deletes it,
  249.      fixing up the pointer from the previous vertex.
  250.    **/
  251. {
  252.     short hashcode;
  253.     VERTEX *vertex, *prev;    /* used to chase down the vertex chain */
  254.  
  255.     hashcode = hash(name);
  256.     vertex = digraph->hashtbl[hashcode];
  257.  
  258.     if (strcmp(vertex->name, name) == 0) /* vertex is first in list */
  259.     {
  260.         digraph->hashtbl[hashcode] = vertex->next;
  261.         dispose(vertex->name);
  262.         dispose(vertex);
  263.         return;
  264.     }
  265.  
  266.       /* search through list until name found */
  267.     vertex = digraph->hashtbl[hashcode];
  268.  
  269.     while (vertex != NULL && (strcmp(vertex->name, name) != 0))
  270.     {
  271.         prev = vertex;
  272.         vertex = vertex->next;
  273.     }
  274.  
  275.     if (vertex != NULL)        /* found it */
  276.     {
  277.         prev->next = vertex->next;
  278.         dispose(vertex->name);
  279.         dispose(vertex);
  280.         return;
  281.     }
  282.  
  283.     PrintError("dispose_vertex: name not found");
  284. } /* dispose_vertex */
  285.  
  286. dispose_edge(digraph, from_node, to_node, ord)
  287. DIGRAPH *digraph;
  288. NODE *from_node, *to_node;
  289. int ord;
  290.   /**
  291.      dispose_edge removes the edge with ordinality ord from the out_edge list 
  292.      of from_node and from the in_edge list of to_node.  If either node is 
  293.      a dummy node, return, since dummy nodes have no edge lists.  Coalescer
  294.      nodes have no edge lists, but their component nodes do, so fix up edge 
  295.      lists of the component nodes recursively.
  296.    **/
  297. {
  298.     VNO from_vno, to_vno;
  299.     NODE *from, *to;
  300.     char **attr;    /* user-defined attributes of edge being deleted */
  301.     BRUSH db;
  302.     COLOR dc;
  303.     int max;
  304.  
  305.     from_vno = Vno(from_node);
  306.     to_vno  = Vno(to_node);
  307.  
  308.     if (Is_dummy(from_node) || Is_dummy(to_node))
  309.     {
  310.     return;
  311.     }
  312.  
  313.     if (!Coalescer(from_node) && !Coalescer(to_node))
  314.     {
  315.     attr = dispose_out_edge(from_node, to_vno, ord, &db, &dc);
  316.     dispose_attr(attr, NEdgeAttr(digraph));
  317.         dispose_in_edge(to_node, from_vno, ord);
  318.     return;
  319.     }
  320.     else if (Coalescer(from_node))
  321.     {
  322.       /**
  323.          ordinality for edges from a coalescer node is figured
  324.          by adding the ordinality of the edge to the sum of the 
  325.          maximum ordinalities of the preceding nodes.  So, if 
  326.          a coalescer has 3 elements, A, B, and C, and we're looking
  327.          at the edges to D, of which A has 2, B has 1, and C has 2,
  328.          the ordinalities of the edges will be:
  329.         A: 1-2
  330.         B: 3
  331.         C: 4-5
  332.          assuming Vno(A) < Vno(B) < Vno(C).
  333.        **/
  334.     each_element(Expansion(from_node), from_vno)
  335.     loop
  336.         from = Node(digraph, from_vno);
  337.  
  338.         if (ord <= (max = max_edges(from, to_node)))
  339.         {
  340.         dispose_edge(digraph, from, to_node, ord);
  341.         break;
  342.         }
  343.         else
  344.         {
  345.         ord -= max;
  346.         }
  347.     endloop
  348.  
  349.     return;
  350.     }
  351.     else if (Coalescer(to_node))
  352.     {
  353.     each_element(Expansion(to_node), to_vno)
  354.     loop
  355.         to = Node(digraph, to_vno);
  356.  
  357.         if (ord <= (max = max_edges(from_node, to)))
  358.         {
  359.         dispose_edge(digraph, from_node, to, ord);
  360.         break;
  361.         }
  362.         else
  363.         {
  364.         ord -= max;
  365.         }
  366.     endloop
  367.  
  368.     return;
  369.     }
  370. } /* dispose_edge */
  371.    
  372. char **dispose_out_edge(node, vno, ord, pb, pc)
  373. NODE *node;
  374. VNO vno;
  375. int ord;
  376. BRUSH *pb;
  377. COLOR *pc;
  378.   /**
  379.      dispose of the edge from node to vno of ordinality ord.
  380.      Just chase down the outedge list until you find a match.
  381.      Set the values for the brush and color, and return the attributes.
  382.    **/
  383. {
  384.     OUTEDGE *edge, *first_edge, *prev_edge;
  385.     char **attr;            /* edge attributes */
  386.  
  387.       /* check if it's the first outedge */
  388.     if (To_vno(node->out_edges) == vno && Ord(node->out_edges) == ord)
  389.     {
  390.         first_edge = node->out_edges;
  391.         node->out_edges = first_edge->next;
  392.         attr = first_edge->attributes;
  393.         *pb = Brush(first_edge);
  394.         *pc = Color(first_edge);
  395.         dispose(first_edge);
  396.         return (attr);
  397.     }
  398.  
  399.     prev_edge = NULL;        /* dummy value, for first pass */
  400.  
  401.       /* now check the rest of the list */
  402.     all_out_edges(node, edge)
  403.     loop
  404.         if (To_vno(edge) == vno && Ord(edge) == ord)
  405.         {
  406.         prev_edge->next = edge->next;
  407.             attr = edge->attributes;
  408.             *pb = Brush(edge);
  409.             *pc = Color(edge);
  410.             dispose(edge);
  411.             return (attr);
  412.         }
  413.  
  414.         prev_edge = edge;
  415.     endloop
  416.  
  417.     if (debug)
  418.     {
  419.         printf("dispose_out_edge:  edge not found\n");
  420.     }
  421.  
  422.     return (NULL);
  423. } /* dispose_out_edge */
  424.  
  425. dispose_in_edge(node, vno, ord)
  426. NODE *node;
  427. VNO vno;
  428. int ord;
  429.   /**
  430.      dispose of the inedge from node to vno with ordinality ord.
  431.      Just chase down the inedge list until you find a match.
  432.    **/
  433. {
  434.     INEDGE *edge, *first_edge, *prev_edge;
  435.  
  436.       /* check the first inedge */
  437.     if (From_vno(node->in_edges) == vno && Ord(node->in_edges) == ord)
  438.     {
  439.         first_edge = node->in_edges;
  440.         node->in_edges = first_edge->next;
  441.         dispose(first_edge);
  442.         return;
  443.     }
  444.  
  445.     prev_edge = NULL;        /* dummy value, for first pass */
  446.  
  447.       /* check the other inedges */
  448.     all_in_edges(node, edge)
  449.     loop
  450.         if (From_vno(edge) == vno && Ord(edge) == ord)
  451.         {
  452.         prev_edge->next = edge->next;
  453.             dispose(edge);
  454.         return;
  455.         }
  456.  
  457.         prev_edge = edge;
  458.     endloop
  459.  
  460.     if (debug)
  461.     {
  462.         printf("dispose_in_edge:  edge not found\n");
  463.     }
  464. } /* dispose_in_edge */
  465.  
  466. remove_ante_links(digraph, node, prev_node)
  467. DIGRAPH *digraph;
  468. NODE *node, *prev_node;
  469.   /**
  470.      remove_ante_links follows the chain of ancestor edges from node through
  471.      prev through the prev non-dummy node, deleting all edges and dummy
  472.      nodes along the way.
  473.    **/
  474. {
  475.     NODE *curr, *prev;
  476.  
  477.     remove_link(prev_node, node);
  478.     curr = prev_node;
  479.  
  480.     while (Is_dummy(curr))
  481.     {
  482.         prev = prev_dummy(digraph, curr);
  483.         remove_link(prev, curr);
  484.         dispose_node(digraph, curr);
  485.         curr = prev;
  486.     }
  487. } /* remove_ante_links */
  488.  
  489. remove_succ_links(digraph, node, next_node)
  490. DIGRAPH *digraph;
  491. NODE *node, *next_node;
  492.   /** 
  493.      remove_succ_links follows the chain of successor edges from node through
  494.      next through the next non-dummy node, deleting all edges and dummy
  495.      nodes along the way.
  496.    **/
  497. {
  498.     NODE *curr, *next;
  499.  
  500.     remove_link(node, next_node);
  501.     curr = next_node;
  502.  
  503.     while (Is_dummy(curr))
  504.     {
  505.         next = next_dummy(digraph, curr);
  506.         remove_link(curr, next);
  507.         dispose_node(digraph, curr);
  508.         curr = next;
  509.     }
  510. } /* remove_succ_links */
  511.  
  512. remove_link(from_node, to_node)
  513. NODE *from_node, *to_node;
  514.   /**
  515.      remove_link removes an edge between two nodes by removing the
  516.      appropriate elements from their successor and ancestor sets.
  517.      Recursively works for coalescer nodes, too.
  518.    **/
  519. {
  520.     VNO vno;
  521.  
  522.     if (Coalescer(from_node))
  523.     {
  524.     each_element(Expansion(from_node), vno)
  525.     loop
  526.         remove_link(Node(digraph, vno), to_node);
  527.     endloop;
  528.     }
  529.  
  530.     if (Coalescer(to_node))
  531.     {
  532.     each_element(Expansion(to_node), vno)
  533.     loop
  534.         remove_link(from_node, Node(digraph, vno));
  535.     endloop;
  536.     }
  537.  
  538.     remove_element(Succ_set(from_node), Vno(to_node));
  539.     remove_element(Ante_set(to_node), Vno(from_node));
  540. } /* remove_link */
  541.  
  542. NODE *get_prev_node(digraph, node)
  543. DIGRAPH *digraph;
  544. NODE *node;
  545.   /** 
  546.      get_prev_node returns a pointer to the previous non-dummy node, working
  547.      back from (dummy node) node.
  548.    **/
  549. {
  550.     NODE *prev_node;
  551.  
  552.     if ((prev_node = prev_dummy(digraph, node)) == NULL)
  553.     {
  554.     return NULL;
  555.     }
  556.  
  557.     while (Is_dummy(prev_node))
  558.     {
  559.     if ((prev_node = prev_dummy(digraph, prev_node)) == NULL)
  560.     {
  561.         return NULL;
  562.     }
  563.     }
  564.  
  565.     return (prev_node);
  566. } /* get_prev_node */
  567.  
  568. NODE *get_next_node(digraph, node)
  569. DIGRAPH *digraph;
  570. NODE *node;
  571.   /** 
  572.      get_next_node returns a pointer to the next non-dummy node, working
  573.      forward from (dummy node) node.
  574.    **/
  575. {
  576.     NODE *next_node;
  577.  
  578.     if ((next_node = next_dummy(digraph, node)) == NULL)
  579.     {
  580.     return NULL;
  581.     }
  582.  
  583.     while (Is_dummy(next_node))
  584.     {
  585.     if ((next_node = next_dummy(digraph, next_node)) == NULL)
  586.     {
  587.         return NULL;
  588.     }
  589.     }
  590.  
  591.     return (next_node);
  592. } /* get_next_node */
  593.  
  594. remove_from_level(digraph, node)
  595. DIGRAPH *digraph;
  596. NODE *node;
  597.   /**
  598.      remove_from_level unlinks a node from a level and fixes the pointers
  599.      from/to the previous and next node on the level.
  600.    **/
  601. {
  602.     LEVEL *level;
  603.  
  604.     level = find_level(digraph, Vno(node));
  605.  
  606.     if (level == NULL)
  607.     {
  608.     return;
  609.     }
  610.  
  611.     if (Prev_member(node) != NULL)
  612.     {
  613.     Next_member(Prev_member(node)) = Next_member(node);
  614.     if (Next_member(node) != NULL)
  615.         Prev_member(Next_member(node)) = Prev_member(node);
  616.     }
  617.     else /* Prev_member(node) is NULL */
  618.     {
  619.     Order(level) = Next_member(node);
  620.     if (Next_member(node) != NULL)
  621.         Prev_member(Next_member(node)) = NULL;
  622.     }
  623.  
  624.     remove_element(Members(level), Vno(node));
  625. } /* remove_from_level */
  626.  
  627. dispose_digraph(digraph)
  628. DIGRAPH *digraph;
  629.   /**
  630.      dispose_digraph steps through a digraph structure and frees up
  631.      all the space.
  632.    **/
  633. {
  634.     NODE *node;
  635.     OUTEDGE *out_edge;
  636.     INEDGE *in_edge;
  637.     LEVEL *level;
  638.  
  639.     if (digraph == NULL)
  640.     {
  641.         return;
  642.     }
  643.  
  644.     dispose_attr(digraph->node_att_names, NNodeAttr(digraph));
  645.     dispose_attr(digraph->edge_att_names, NEdgeAttr(digraph));
  646.  
  647.     all_nodes(digraph, node)
  648.     loop
  649.         dispose(Ante_set(node));
  650.         dispose(Succ_set(node));
  651.         dispose(Expansion(node));
  652.         dispose(Name(node));
  653.         dispose(Text(node));
  654.         dispose(node->vertex);
  655.  
  656.         all_out_edges(node, out_edge)
  657.         loop
  658.         dispose_attr(out_edge->attributes, NEdgeAttr(digraph));
  659.         dispose(out_edge);
  660.         endloop
  661.  
  662.         all_in_edges(node, in_edge)
  663.         loop
  664.         dispose(in_edge);
  665.         endloop
  666.  
  667.         dispose(node);
  668.     endloop
  669.  
  670.     each_level(digraph, level)
  671.     loop
  672.         dispose(Members(level));
  673.         dispose(level);
  674.     endloop
  675.  
  676.     dispose(Title(digraph));
  677.     dispose (digraph);
  678. } /* dispose_digraph */
  679.